#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;

namespace Wang
{

template<class T>
struct list_node
{
    T _data;
    list_node* _next;
    list_node* _prev;

    list_node(const T& x = T())
        :_data(x)
        ,_next(this)
        ,_prev(this)
    {}
};


template<class T>
struct list_iterator
{
    typedef list_node<T> node;
    using iterator_category = std::bidirectional_iterator_tag; // 迭代器类别：双向迭代器（可以向前和向后移动）
    using value_type = T; // 指定迭代器指向的元素的类型
    using difference_type = std::ptrdiff_t; // 两个迭代器之间距离的类型，一般就是整数
    using pointer = T*;     // 指针类型
    using reference = T&;   // 元素的引用类型

    node* _ptr;
    list_iterator(node* p)
        :_ptr(p)
    {}

    // 这里最好将加上const，可能有const list_iterator的情况
    T& operator*() const { return _ptr->_data; }
    T* operator->() const { return &(_ptr->_data); }

    list_iterator& operator++()
    {
        _ptr = _ptr->_next;
        return *this;
    }
    // 后置++/--注意传值返回
    list_iterator operator++(int)
    {
        list_iterator tmp(*this); // 用编译器生成的拷贝构造就行
        _ptr = _ptr->_next;
        return tmp;
    }

    list_iterator& operator--()
    {
        _ptr = _ptr->_prev;
        return *this;
    }
    list_iterator operator--(int)
    {
        list_iterator tmp(*this); // 用编译器生成的拷贝构造就行
        _ptr = _ptr->_prev;
        return tmp;
    }

    bool operator!= (const list_iterator& it) const
    { return _ptr != it._ptr; }

    bool operator== (const list_iterator& it) const
    { return _ptr == it._ptr; }
};

template<class T>
struct list_const_iterator
{
    typedef list_node<T> node;

    using iterator_category = std::bidirectional_iterator_tag; // 迭代器类别：双向迭代器（可以向前和向后移动）
    using value_type = const T; // 指定迭代器指向的元素的类型
    using difference_type = std::ptrdiff_t; // 两个迭代器之间距离的类型，一般就是整数
    using pointer = const T*;     // 指针类型
    using reference = const T&;   // 元素的引用类型
    
    const node* _ptr;
    list_const_iterator(const node* p)
        :_ptr(p)
    {}

    // 可能会出现这样的情况：
    // list<int> ls1 = { 1,2,3,4,5 };
    // list<int>::const_iterator it = ls1.begin();
    // ls1.begin()返回的是list<int>::iterator, 所有要提供下面的构造
    list_const_iterator(const list_iterator<T>& lt)
        :_ptr(lt._ptr)
    {}

    const T& operator*() const { return _ptr->_data; }
    const T* operator->() const { return &(_ptr->_data); }

    list_const_iterator& operator++()
    {
        _ptr = _ptr->_next;
        return *this;
    }
    list_const_iterator operator++(int)
    {
        list_const_iterator tmp(*this); // 用编译器生成的拷贝构造就行
        _ptr = _ptr->_next;
        return tmp;
    }

    list_const_iterator& operator--()
    {
        _ptr = _ptr->_prev;
        return *this;
    }
    list_const_iterator operator--(int)
    {
        list_const_iterator tmp(*this); // 用编译器生成的拷贝构造就行
        _ptr = _ptr->_prev;
        return tmp;
    }

    bool operator!= (const list_const_iterator& it) const
    { return _ptr != it._ptr; }

    bool operator== (const list_const_iterator& it) const
    { return _ptr == it._ptr; }
};

template<class T>
class list
{
    typedef list_node<T> node;

    node* _head = new node; // 带头双向循环链表
public:
    list() {}
    list(initializer_list<T> il)
    {
        for(auto& e : il)
            push_back(e);
    }


    ~list()
    {
        // node* i = _head->_next;
        // while(i != _head)
        // {
        //     node* ne = i->_next;
        //     delete i;
        //     i = ne;
        // }
        clear();
        delete _head;
        _head = nullptr;
    }

    void clear()
    {
        auto it = begin();
        while(it != end())
            it = erase(it); // erase的返回值是被删除元素的下一个元素的迭代器
    }
    list(const list& ls)
    {
        for(auto& e : ls)
            push_back(e);
    }

    void swap(list& ls) { std::swap(_head, ls._head); }

    list operator= (const list& ls)
    {
        // 避免自己给自己赋值
        if(this != &ls)
        {
            list tmp(ls);
            swap(tmp);
        }
        return *this;
    }

    void print()
    {
        for(auto& e : (*this))
            cout << e << ' ';
        cout << endl;
    }

    typedef list_iterator<T> iterator;
    typedef list_const_iterator<T> const_iterator;
    iterator begin() { return _head->_next; }
    iterator end() { return _head; }
    const_iterator begin() const { return _head->_next; }
    const_iterator end() const { return _head; }

    bool empty() const { return _head->_next == _head; }

    // 在pos位置前插入x，返回指向第一个新插入元素的迭代器。原迭代器未失效
    iterator insert(iterator pos, const T& x)
    {
        node* new_node = new node(x);
        node* prev = pos._ptr->_prev;
        new_node->_next = pos._ptr;
        new_node->_prev = prev;
        prev->_next = pos._ptr->_prev = new_node;
        return new_node;
    }

    // 删除pos位置元素, 返回指向被删除元素的下一个元素的迭代器。原迭代器失效
    iterator erase(iterator pos)
    {
        assert(pos != end());
        node* prev = pos._ptr->_prev;
        node* next = pos._ptr->_next;
        prev->_next = next;
        next->_prev = prev;
        delete pos._ptr;
        return next;
    }

    void push_back(const T& x) { insert(end(), x); }
    void pop_back() { erase(--end()); }
    void push_front(const T& x) { insert(begin(), x); }
    void pop_front() { erase(begin()); }
};

} // namespace Wang